#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"
#include "TypeDefin.h"

using namespace std;

/*
 * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。



示例 1:



输入: head = [-10,-3,0,5,9]
输出: [0,-3,9,-10,null,5]
解释: 一个可能的答案是[0，-3,9，-10,null,5]，它表示所示的高度平衡的二叉搜索树。
示例 2:

输入: head = []
输出: []
 *
 *
 *
 * */

ListNode *findMid(ListNode *head, ListNode *end) {


    ListNode *fast = head;
    ListNode *slow = head;

    ///我这边这个写错了 slow是不能返回null的 要不下面得判断了 出现一系列问题

    while (fast != end && fast->next != end) {
        slow = slow->next;
        fast = fast->next;
        fast = fast->next;
    }

    return slow;
}


TreeNode *buildTree(ListNode *start, ListNode *end) {
    //这个也是个关键
    if (!start || start == end)
        return nullptr;

    auto mid = findMid(start, end);

    auto root = new TreeNode(mid->val);
    root->left = buildTree(start, mid);
    root->right = buildTree(mid->next, end);

    return root;
}

TreeNode *sortedListToBST(ListNode *head) {
    return buildTree(head, nullptr);
}